# base cases n = len(nums) if n * k == 0: return [] if k == 1: return nums
defclean_deque(i): # remove indexes of elements not from sliding window if deq and deq[0] == i - k: deq.popleft() # remove from deq indexes of all elements # which are smaller than current element nums[i] while deq and nums[i] > nums[deq[-1]]: deq.pop()
# init deque and output deq = deque() max_idx = 0 for i in range(k): clean_deque(i) deq.append(i) # compute max in nums[:k] if nums[i] > nums[max_idx]: max_idx = i output = [nums[max_idx]]
# build output for i in range(k, n): clean_deque(i) deq.append(i) output.append(nums[deq[0]]) return output
比官方解法看起来更简洁一点的
1 2 3 4 5 6 7 8 9
deque = collections.deque() res = [] for i, num in enumerate(nums): while deque and deque[0] <= i - k: deque.popleft() # outdate indices # 'while' can be changed into 'if' while deque and num > nums[deque[-1]]: deque.pop() deque.append(i) if i >= k - 1: res.append(nums[deque[0]]) return res
n = len(nums) if n * k == 0: return [] if k == 1: return nums
left = [0] * n left[0] = nums[0] right = [0] * n right[n - 1] = nums[n - 1] for i in range(1, n): # from left to right if i % k == 0: # block start left[i] = nums[i] else: left[i] = max(left[i - 1], nums[i]) # from right to left j = n - i - 1 if (j + 1) % k == 0: # block end right[j] = nums[j] else: right[j] = max(right[j + 1], nums[j])
output = [] for i in range(n - k + 1): output.append(max(left[i + k - 1], right[i]))
# 哈希集合，记录每个字符是否出现过 occ = set() n = len(s) # 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动 rk, ans = -1, 0 for i in range(n): if i != 0: # 左指针向右移动一格，移除一个字符 occ.remove(s[i - 1]) while rk + 1 < n and s[rk + 1] notin occ: # 不断地移动右指针 occ.add(s[rk + 1]) rk += 1 # 第 i 到 rk 个字符是一个极长的无重复字符子串 ans = max(ans, rk - i + 1) return ans
k, res, c_dict = -1, 0, {} for i, c in enumerate(s): if c in c_dict and c_dict[c] > k: # 字符c在字典中 且 上次出现的下标大于当前长度的起始下标 k = c_dict[c] c_dict[c] = i else: c_dict[c] = i res = max(res, i-k) return res
res = [] window = {} # 记录窗口中各个字符数量的字典 needs = {} # 记录目标字符串中各个字符数量的字典 for c in p: needs[c] = needs.get(c, 0) + 1# 统计目标字符串的信息
length, limit = len(p), len(s) left = right = 0# 定理两个指针，分别表示窗口的左、右界限
while right < limit: c = s[right] if c notin needs: # 当遇到不需要的字符时 window.clear() # 将之前统计的信息全部放弃 left = right = right + 1# 从下一位置开始重新统计 else: window[c] = window.get(c, 0) + 1# 统计窗口内各种字符出现的次数 if right-left+1 == length: # 当窗口大小与目标字符串长度一致时 if window == needs: res.append(left) # 如果窗口内的各字符数量与目标字符串一致就将left添加到结果中 window[s[left]] -= 1# 并将移除的字符数量减一 left += 1# left右移 right += 1# right右移 return res
另一种写法：用数组比较是否相等。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
# 记录p, s字母个数 p_count = [0] * 26 s_count = [0] * 26 res = [] for a in p: p_count[ord(a) - 97] += 1 left = 0 for right in range(len(s)): # print(p_count, s_count) if right < len(p) - 1: s_count[ord(s[right]) - 97] += 1 continue # 窗口加一个， 减一个，维护长度为len(p)的长度 s_count[ord(s[right]) - 97] += 1 if p_count == s_count: res.append(left) s_count[ord(s[left]) - 97] -= 1 left += 1 return res
哈希表+前缀：按前缀统计字母的个数，这样便可方便求出和p等长的字符串是否一致。
1 2 3 4 5 6 7 8 9 10 11 12
from collections import Counter n = len(p) p = Counter(p) dp = [0] * (len(s) + 1) dp[0] = Counter() res = [] for i in range(1, len(s) + 1): dp[i] = dp[i - 1].copy() dp[i][s[i - 1]] += 1 if i >= n and dp[i] - dp[i - n] == p: res.append(i - n) return res